#include <vector>
using namespace std;
void backtrace(vector<int> &candidates, vector<vector<int>> &res,
               vector<int> &selected, int target, int cur) {

  if (target == 0) {
    res.push_back(selected);
    return;
  }
  if (target < 0)
    return;
  for (int i = cur; i < candidates.size(); ++i) {
    selected.push_back(candidates[i]);
    backtrace(candidates, res, selected, target - candidates[i], i);
    selected.pop_back();
  }
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
  if (target <= 0)
    return {};
  vector<vector<int>> res;
  vector<int> selected;
  backtrace(candidates, res, selected, target, 0);
  return res;
}
